{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Greatest Common Divisor Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #array #math #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #数组 #数学 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canTraverseAllPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大公约数遍历"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;，你可以在一些下标之间遍历。对于两个下标&nbsp;<code>i</code>&nbsp;和&nbsp;<code>j</code>（<code>i != j</code>），当且仅当&nbsp;<code>gcd(nums[i], nums[j]) &gt; 1</code>&nbsp;时，我们可以在两个下标之间通行，其中&nbsp;<code>gcd</code>&nbsp;是两个数的 <strong>最大公约数</strong>&nbsp;。</p>\n",
    "\n",
    "<p>你需要判断 <code>nums</code>&nbsp;数组中&nbsp;<strong>任意&nbsp;</strong>两个满足 <code>i &lt; j</code>&nbsp;的下标&nbsp;<code>i</code>&nbsp;和&nbsp;<code>j</code> ，是否存在若干次通行可以从 <code>i</code>&nbsp;遍历到 <code>j</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果任意满足条件的下标对都可以遍历，那么返回 <code>true</code>&nbsp;，否则返回 <code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,3,6]\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>这个例子中，总共有 3 个下标对：(0, 1) ，(0, 2) 和 (1, 2) 。\n",
    "从下标 0 到下标 1 ，我们可以遍历 0 -&gt; 2 -&gt; 1 ，我们可以从下标 0 到 2 是因为 gcd(nums[0], nums[2]) = gcd(2, 6) = 2 &gt; 1 ，从下标 2 到 1 是因为 gcd(nums[2], nums[1]) = gcd(6, 3) = 3 &gt; 1 。\n",
    "从下标 0 到下标 2 ，我们可以直接遍历，因为 gcd(nums[0], nums[2]) = gcd(2, 6) = 2 &gt; 1 。同理，我们也可以从下标 1 到 2 因为 gcd(nums[1], nums[2]) = gcd(3, 6) = 3 &gt; 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [3,9,5]\n",
    "<b>输出：</b>false\n",
    "<b>解释：</b>我们没法从下标 0 到 2 ，所以返回 false 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [4,3,12,8]\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>总共有 6 个下标对：(0, 1) ，(0, 2) ，(0, 3) ，(1, 2) ，(1, 3) 和 (2, 3) 。所有下标对之间都存在可行的遍历，所以返回 true 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [greatest-common-divisor-traversal](https://leetcode.cn/problems/greatest-common-divisor-traversal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [greatest-common-divisor-traversal](https://leetcode.cn/problems/greatest-common-divisor-traversal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,6]', '[3,9,5]', '[4,3,12,8]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        if 1 in nums:\n",
    "            return len(nums) == 1\n",
    "        prime = [2, 3, 5, 7]\n",
    "        for i in range(11, int(sqrt(max(nums))) + 1):\n",
    "            isPrime = 1\n",
    "            for x in prime:\n",
    "                if x * x > i:\n",
    "                    break\n",
    "                if i % x == 0:\n",
    "                    isPrime = 0\n",
    "                    break\n",
    "            if isPrime:\n",
    "                prime.append(i)\n",
    "        UFS = {}\n",
    "        for x in nums:\n",
    "            factor = []\n",
    "            for y in prime:\n",
    "                if y * y > x:\n",
    "                    break\n",
    "                if x % y == 0:\n",
    "                    factor.append(y)\n",
    "                    while x % y == 0:\n",
    "                        x //= y\n",
    "            if x != 1:\n",
    "                factor.append(x)\n",
    "            for x in factor:\n",
    "                if x not in UFS:\n",
    "                    UFS[x] = x\n",
    "            for i in range(1, len(factor)):\n",
    "                stack1, stack2 = [factor[0]], [factor[i]]\n",
    "                while UFS[stack1[-1]] != stack1[-1]:\n",
    "                    stack1.append(UFS[stack1[-1]])\n",
    "                while UFS[stack2[-1]] != stack2[-1]:\n",
    "                    stack2.append(UFS[stack2[-1]])\n",
    "                root = stack1.pop()\n",
    "                while stack2:\n",
    "                    UFS[stack2.pop()] = root\n",
    "                while stack1:\n",
    "                    UFS[stack1.pop()] = root\n",
    "        return sum(UFS[x] == x for x in UFS) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        if len(nums)==1:\n",
    "            return True\n",
    "        now=nums[0]\n",
    "        last=-1\n",
    "        num=0\n",
    "        while now!=last:\n",
    "            last=now\n",
    "            num=0\n",
    "            for i,x in enumerate(nums):\n",
    "                tmp=gcd(now,x)\n",
    "                if tmp>1:\n",
    "                    num+=1\n",
    "                    now*=(x//tmp)\n",
    "                # print(now)\n",
    "        return num==len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        N = len(nums)\n",
    "        \n",
    "        t = nums.pop()\n",
    "        \n",
    "        while nums:\n",
    "            nxt = []\n",
    "            for n in nums:\n",
    "                if math.gcd(n, t) != 1:\n",
    "                    t = math.lcm(n, t)\n",
    "                else:\n",
    "                    nxt.append(n)\n",
    "            \n",
    "            if len(nxt) == len(nums):\n",
    "                break\n",
    "            nums = nxt\n",
    "                \n",
    "        return not bool(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = isqrt(10**5) + 1\n",
    "isprime = [True] * (MX + 1)\n",
    "primes = []\n",
    "for num in range(2, MX + 1):\n",
    "    if isprime[num]:\n",
    "        primes.append(num)\n",
    "    for p in primes:\n",
    "        if num * p > MX:\n",
    "            break\n",
    "        isprime[num * p] = False\n",
    "        if num % p == 0:\n",
    "            break\n",
    "\n",
    "# 并查集\n",
    "class DSU:\n",
    "    __slots__ = {'num', 'pa', 'rank'}\n",
    "    def __init__(self, n):\n",
    "        self.num = n\n",
    "        self.pa = list(range(n))\n",
    "        self.rank = [0] * n\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.num\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.pa[x] != x:\n",
    "            self.pa[x] = self.find(self.pa[x])\n",
    "        return self.pa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        # 按秩合并\n",
    "        rx, ry = self.find(x), self.find(y)\n",
    "        if rx != ry:\n",
    "            if self.rank[rx] < self.rank[ry]:\n",
    "                rx, ry = ry, rx\n",
    "            self.pa[ry] = rx\n",
    "            if self.rank[rx] == self.rank[ry]:\n",
    "                self.rank[rx] += 1\n",
    "            self.num -= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        dsu = DSU(n)\n",
    "        for p in primes:\n",
    "            pre = -1\n",
    "            for i in range(n):\n",
    "                if nums[i] == 1:\n",
    "                    continue\n",
    "                if nums[i] % p == 0:\n",
    "                    if pre != -1:\n",
    "                        dsu.union(pre, i)\n",
    "                    pre = i\n",
    "                    while nums[i] % p == 0:\n",
    "                        nums[i] //= p\n",
    "        \n",
    "        last = {}\n",
    "        for i, x in enumerate(nums):\n",
    "            if x > 1:\n",
    "                if x not in last:\n",
    "                    last[x] = i\n",
    "                else:\n",
    "                    dsu.union(last[x], i)\n",
    "\n",
    "        return len(dsu) == 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "import sys\n",
    "import random\n",
    "# sys.setrecursionlimit(100000)\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class UF:\n",
    "    def __init__(self,n) -> None:\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.rank = [1] * n\n",
    "    def find(self,x):\n",
    "        if x == self.parent[x]:\n",
    "            return x\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    def merge(self,x,y):\n",
    "        x,y = self.find(x),self.find(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        self.rank[y] += self.rank[x]\n",
    "        self.rank[x] = 0\n",
    "        self.parent[x] = y\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        d = [-1] * int(max(nums) + 1) # 若nums中某个数存在质因子 x, 则d[x]记录对应的是其中一个下标\n",
    "        n = len(nums)\n",
    "        uf = UF(n)\n",
    "        for i,num in enumerate(nums):\n",
    "            j = 2\n",
    "            while j * j <= num:\n",
    "                if num % j == 0:\n",
    "                    if d[j] != -1:\n",
    "                        uf.merge(i, d[j])\n",
    "                    else:\n",
    "                        d[j] = i\n",
    "                    while num % j == 0:\n",
    "                        num //= j\n",
    "                j += 1\n",
    "            if num > 1:\n",
    "                if d[num] != -1:\n",
    "                    uf.merge(i, d[num])\n",
    "                else:\n",
    "                    d[num] = i\n",
    "        for i in range(n):\n",
    "            if uf.rank[uf.find(i)] == n:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "import sys\n",
    "import random\n",
    "# sys.setrecursionlimit(100000)\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class UF:\n",
    "    def __init__(self,n) -> None:\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.rank = [1] * n\n",
    "    def find(self,x):\n",
    "        if x == self.parent[x]:\n",
    "            return x\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    def merge(self,x,y):\n",
    "        x,y = self.find(x),self.find(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        self.rank[y] += self.rank[x]\n",
    "        self.rank[x] = 0\n",
    "        self.parent[x] = y\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        d = [-1] * int(max(nums) + 1)\n",
    "        n = len(nums)\n",
    "        uf = UF(n)\n",
    "        for i,num in enumerate(nums):\n",
    "            j = 2\n",
    "            while j * j <= num:\n",
    "                if num % j == 0:\n",
    "                    if d[j] != -1:\n",
    "                        uf.merge(i, d[j])\n",
    "                    else:\n",
    "                        d[j] = i\n",
    "                    while num % j == 0:\n",
    "                        num //= j\n",
    "                j += 1\n",
    "            if num > 1:\n",
    "                if d[num] != -1:\n",
    "                    uf.merge(i, d[num])\n",
    "                else:\n",
    "                    d[num] = i\n",
    "        for i in range(n):\n",
    "            if uf.rank[uf.find(i)] == n:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_prime(max: int) -> list:\n",
    "    prime_vals = []\n",
    "    flag = [True] * (max+1)\n",
    "    for val in range(2, max+1):\n",
    "        if flag[val]:\n",
    "            prime_vals.append(val)\n",
    "        for p in prime_vals:\n",
    "            if (idx := val * p) > max: \n",
    "                break\n",
    "            flag[idx] = False\n",
    "            if val % p == 0:\n",
    "                break\n",
    "    return prime_vals\n",
    "primes = get_prime(1000)\n",
    "def devide(val):\n",
    "    ans = []\n",
    "    for i in primes:\n",
    "        if i*i>val:\n",
    "            break\n",
    "        if val % i==0:\n",
    "            while val % i==0:\n",
    "                val //= i\n",
    "            ans.append(i)\n",
    "        if val == 1:\n",
    "            break\n",
    "    if val != 1:\n",
    "        ans.append(val)\n",
    "    return ans\n",
    "        \n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        if len(nums) == 1:\n",
    "            return True\n",
    "        if 1 in nums:\n",
    "            return False\n",
    "        nums = list(set(nums))\n",
    "        edges = set()\n",
    "        pset = set()\n",
    "        for v in nums:\n",
    "            dvd = devide(v)\n",
    "            for p in dvd:\n",
    "                pset.add(p)\n",
    "            k = len(dvd)\n",
    "            for i in range(k-1):\n",
    "                for j in range(i+1, k):\n",
    "                    a, b = dvd[i], dvd[j]\n",
    "                    edges.add((a, b))\n",
    "        p = {}\n",
    "        for x in pset:\n",
    "            p[x] = x\n",
    "        def rt(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = rt(p[x])\n",
    "            return p[x]\n",
    "        def merge(a, b):\n",
    "            aa, bb = rt(a), rt(b)\n",
    "            if aa != bb:\n",
    "                p[aa] = bb\n",
    "        for a, b in edges:\n",
    "            merge(a, b)\n",
    "        rt_set = set()\n",
    "        for x in pset:\n",
    "            rt_set.add(rt(x))\n",
    "            if len(rt_set) >= 2:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_prime(max: int) -> list:\n",
    "    prime_vals = []\n",
    "    flag = [True] * (max+1)\n",
    "    for val in range(2, max+1):\n",
    "        if flag[val]:\n",
    "            prime_vals.append(val)\n",
    "        for p in prime_vals:\n",
    "            if (idx := val * p) > max: \n",
    "                break\n",
    "            flag[idx] = False\n",
    "            if val % p == 0:\n",
    "                break\n",
    "    return prime_vals\n",
    "primes = get_prime(1000)\n",
    "def devide(val):\n",
    "    ans = []\n",
    "    for i in primes:\n",
    "        if i*i>val:\n",
    "            break\n",
    "        if val % i==0:\n",
    "            while val % i==0:\n",
    "                val //= i\n",
    "            ans.append(i)\n",
    "        if val == 1:\n",
    "            break\n",
    "    if val != 1:\n",
    "        ans.append(val)\n",
    "    return ans\n",
    "        \n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        if len(nums) == 1:\n",
    "            return True\n",
    "        if 1 in nums:\n",
    "            return False\n",
    "        nums = list(set(nums))\n",
    "        edges = set()\n",
    "        pset = set()\n",
    "        for v in nums:\n",
    "            dvd = devide(v)\n",
    "            for p in dvd:\n",
    "                pset.add(p)\n",
    "            k = len(dvd)\n",
    "            for i in range(k-1):\n",
    "                for j in range(i+1, k):\n",
    "                    a, b = dvd[i], dvd[j]\n",
    "                    edges.add((a, b))\n",
    "        p = {}\n",
    "        for x in pset:\n",
    "            p[x] = x\n",
    "        def rt(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = rt(p[x])\n",
    "            return p[x]\n",
    "        def merge(a, b):\n",
    "            aa, bb = rt(a), rt(b)\n",
    "            if aa != bb:\n",
    "                p[aa] = bb\n",
    "        for a, b in edges:\n",
    "            merge(a, b)\n",
    "        rt_set = set()\n",
    "        for x in pset:\n",
    "            rt_set.add(rt(x))\n",
    "            if len(rt_set) >= 2:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "def get_prime(N):\n",
    "    prime_vals = []\n",
    "    flag = [True] * (N+1)\n",
    "    for val in range(2, N+1):\n",
    "        if flag[val]:\n",
    "            prime_vals.append(val)\n",
    "\n",
    "        for p_val in prime_vals:\n",
    "            if val * p_val > N:\n",
    "                break\n",
    "\n",
    "            flag[val * p_val] = False\n",
    "\n",
    "            if val % p_val == 0:\n",
    "                break\n",
    "\n",
    "    return prime_vals\n",
    "\n",
    "primes = get_prime(1000)\n",
    "\n",
    "def devide_prime(val):\n",
    "    ans = []\n",
    "\n",
    "    for i in primes:\n",
    "        if i*i > val:\n",
    "            break\n",
    "\n",
    "        if val % i == 0:\n",
    "            cnt = 0\n",
    "            while val % i == 0:\n",
    "                val //= i\n",
    "                cnt += 1\n",
    "\n",
    "            ans.append((i, cnt))\n",
    "\n",
    "        if val == 1:\n",
    "            break\n",
    "\n",
    "    if val != 1:\n",
    "        ans.append((val, 1))\n",
    "\n",
    "    return ans\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return True\n",
    "\n",
    "        for v in nums:\n",
    "            if v == 1:\n",
    "                return False\n",
    "\n",
    "        nums = list(set(nums))\n",
    "\n",
    "        e = set()\n",
    "        P = set()\n",
    "        for v in nums:\n",
    "            ret = devide_prime(v)\n",
    "            for p, cnt in ret:\n",
    "                P.add(p)\n",
    "\n",
    "            k = len(ret)\n",
    "            for i in range(k):\n",
    "                for j in range(i+1, k):\n",
    "                    a, b = ret[i][0], ret[j][0]\n",
    "                    e.add((a, b))\n",
    "\n",
    "        p = {}\n",
    "        for x in P:\n",
    "            p[x] = x\n",
    "\n",
    "        def rt(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = rt(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        def merge(a, b):\n",
    "            aa, bb = rt(a), rt(b)\n",
    "            if aa != bb:\n",
    "                p[aa] = bb\n",
    "\n",
    "        for a, b in e:\n",
    "            merge(a, b)\n",
    "\n",
    "        rt_set = set()\n",
    "        for x in P:\n",
    "            rt_set.add(rt(x))\n",
    "            if len(rt_set) >= 2:\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "def get_prime(N):\n",
    "    prime_vals = []\n",
    "    flag = [True] * (N+1)\n",
    "    for val in range(2, N+1):\n",
    "        if flag[val]:\n",
    "            prime_vals.append(val)\n",
    "\n",
    "        for p_val in prime_vals:\n",
    "            if val * p_val > N:\n",
    "                break\n",
    "\n",
    "            flag[val * p_val] = False\n",
    "\n",
    "            if val % p_val == 0:\n",
    "                break\n",
    "\n",
    "    return prime_vals\n",
    "\n",
    "primes = get_prime(1000)\n",
    "\n",
    "def devide_prime(val):\n",
    "    ans = []\n",
    "\n",
    "    for i in primes:\n",
    "        if i*i > val:\n",
    "            break\n",
    "\n",
    "        if val % i == 0:\n",
    "            cnt = 0\n",
    "            while val % i == 0:\n",
    "                val //= i\n",
    "                cnt += 1\n",
    "\n",
    "            ans.append((i, cnt))\n",
    "\n",
    "        if val == 1:\n",
    "            break\n",
    "\n",
    "    if val != 1:\n",
    "        ans.append((val, 1))\n",
    "\n",
    "    return ans\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return True\n",
    "\n",
    "        for v in nums:\n",
    "            if v == 1:\n",
    "                return False\n",
    "\n",
    "        nums = list(set(nums))\n",
    "\n",
    "        e = set()\n",
    "        P = set()\n",
    "        for v in nums:\n",
    "            ret = devide_prime(v)\n",
    "            for p, cnt in ret:\n",
    "                P.add(p)\n",
    "\n",
    "            k = len(ret)\n",
    "            for i in range(k):\n",
    "                for j in range(i+1, k):\n",
    "                    a, b = ret[i][0], ret[j][0]\n",
    "                    e.add((a, b))\n",
    "\n",
    "        p = {}\n",
    "        for x in P:\n",
    "            p[x] = x\n",
    "\n",
    "        def rt(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = rt(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        def merge(a, b):\n",
    "            aa, bb = rt(a), rt(b)\n",
    "            if aa != bb:\n",
    "                p[aa] = bb\n",
    "\n",
    "        for a, b in e:\n",
    "            merge(a, b)\n",
    "\n",
    "        rt_set = set()\n",
    "        for x in P:\n",
    "            rt_set.add(rt(x))\n",
    "            if len(rt_set) >= 2:\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "def get_prime(N):\n",
    "    prime_vals = []\n",
    "    flag = [True] * (N+1)\n",
    "    for val in range(2, N+1):\n",
    "        if flag[val]:\n",
    "            prime_vals.append(val)\n",
    "\n",
    "        for p_val in prime_vals:\n",
    "            if val * p_val > N:\n",
    "                break\n",
    "\n",
    "            flag[val * p_val] = False\n",
    "\n",
    "            if val % p_val == 0:\n",
    "                break\n",
    "\n",
    "    return prime_vals\n",
    "\n",
    "primes = get_prime(1000)\n",
    "\n",
    "def devide_prime(val):\n",
    "    ans = []\n",
    "\n",
    "    for i in primes:\n",
    "        if i*i > val:\n",
    "            break\n",
    "\n",
    "        if val % i == 0:\n",
    "            cnt = 0\n",
    "            while val % i == 0:\n",
    "                val //= i\n",
    "                cnt += 1\n",
    "\n",
    "            ans.append((i, cnt))\n",
    "\n",
    "        if val == 1:\n",
    "            break\n",
    "\n",
    "    if val != 1:\n",
    "        ans.append((val, 1))\n",
    "\n",
    "    return ans\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return True\n",
    "\n",
    "        for v in nums:\n",
    "            if v == 1:\n",
    "                return False\n",
    "\n",
    "        nums = list(set(nums))\n",
    "\n",
    "        e = set()\n",
    "        P = set()\n",
    "        for v in nums:\n",
    "            ret = devide_prime(v)\n",
    "            for p, cnt in ret:\n",
    "                P.add(p)\n",
    "\n",
    "            k = len(ret)\n",
    "            for i in range(k):\n",
    "                for j in range(i+1, k):\n",
    "                    a, b = ret[i][0], ret[j][0]\n",
    "                    e.add((a, b))\n",
    "\n",
    "        p = {}\n",
    "        for x in P:\n",
    "            p[x] = x\n",
    "\n",
    "        def rt(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = rt(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        def merge(a, b):\n",
    "            aa, bb = rt(a), rt(b)\n",
    "            if aa != bb:\n",
    "                p[aa] = bb\n",
    "\n",
    "        for a, b in e:\n",
    "            merge(a, b)\n",
    "\n",
    "        rt_set = set()\n",
    "        for x in P:\n",
    "            rt_set.add(rt(x))\n",
    "            if len(rt_set) >= 2:\n",
    "                return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PrimeTable:\n",
    "    def __init__(self, n=int((10**9)**0.5)+3) -> None:\n",
    "        #值域1e9的话考虑质因子，只需小于等于(10**9)**0.5的质数即可\n",
    "        #任意一个正整数n最多只有一个质因子大于根号n\n",
    "        self.n = n\n",
    "        self.primes = [] #小于等于n的所有质数\n",
    "        self.min_div = [0] * (n+1)\n",
    "        self.min_div[1] = 1\n",
    " \n",
    "        mu = [0] * (n+1)\n",
    "        phi = [0] * (n+1)\n",
    "        mu[1] = 1\n",
    "        phi[1] = 1\n",
    " \n",
    "        for i in range(2, n+1):\n",
    "            if not self.min_div[i]:\n",
    "                self.primes.append(i)\n",
    "                self.min_div[i] = i\n",
    "                mu[i] = -1\n",
    "                phi[i] = i-1\n",
    "            for p in self.primes:\n",
    "                if i * p > n: break\n",
    "                self.min_div[i*p] = p\n",
    "                if i % p == 0:\n",
    "                    phi[i*p] = phi[i] * p\n",
    "                    break\n",
    "                else:\n",
    "                    mu[i*p] = -mu[i]\n",
    "                    phi[i*p] = phi[i] * (p - 1)\n",
    "    # x是否质数\n",
    "    def is_prime(self, x:int):\n",
    "        if x < 2: return False\n",
    "        if x <= self.n: return self.min_div[x] == x\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x % i == 0: return False\n",
    "        return True\n",
    "\n",
    "    # x分解质因数:[p, cnt] 质因子p，个数cnt\n",
    "    # 用的yield，当作一个可遍历的数据对象\n",
    "    #一个数一定可以分解为多个质数的连乘积\n",
    "    #n = x^a * y^b * z^c ...  （x,y,z为质因数） n的约数个数=(a+1)(b+1)...(y+1)\n",
    "\n",
    "    def prime_factorization(self, x:int):\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x <= self.n: break\n",
    "            if x % p == 0:\n",
    "                cnt = 0\n",
    "                while x % p == 0: cnt += 1; x //= p\n",
    "                yield p, cnt\n",
    "        while (1 < x and x <= self.n):\n",
    "            p, cnt = self.min_div[x], 0\n",
    "            while x % p == 0: cnt += 1; x //= p\n",
    "            yield p, cnt\n",
    "        if x >= self.n and x > 1:\n",
    "            #小于等于(10**9)**0.5的质数除干净了，如果还大于1\n",
    "            # 那么余下的数一定是一个大于等于n的质数\n",
    "            yield x, 1\n",
    "            \n",
    "    # x的所有因数\n",
    "    def get_factors(self, x:int):\n",
    "        factors = [1]\n",
    "        for p, b in self.prime_factorization(x):\n",
    "            n = len(factors)\n",
    "            for j in range(1, b+1):\n",
    "                for d in factors[:n]:\n",
    "                    factors.append(d * (p ** j))\n",
    "        return factors\n",
    "\n",
    "pt=PrimeTable(10**5+5)\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        if len(nums)==1:\n",
    "            return True\n",
    "        if 1 in nums:\n",
    "            return False\n",
    "        fa={}\n",
    "        def find(a):\n",
    "            if a not in fa:\n",
    "                fa[a]=a\n",
    "            if fa[a]!=a:\n",
    "                fa[a]=find(fa[a])\n",
    "            return fa[a]\n",
    "        for x in nums:\n",
    "            for p,c in pt.prime_factorization(x):\n",
    "                fa[find(x)]=find(p)\n",
    "        return len({find(i) for i in nums})==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UFS:\n",
    "    def __init__(self):\n",
    "        self.root = {}\n",
    "    \n",
    "    def add(self, x):\n",
    "        if x not in self.root:\n",
    "            self.root[x] = x\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.root[x] != x:\n",
    "            self.root[x] = self.find(self.root[x])\n",
    "        return self.root[x]\n",
    "\n",
    "    def union(self, a, b):\n",
    "        ra, rb = self.find(a), self.find(b)\n",
    "        self.root[ra] = rb\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        def prime_factors(n):\n",
    "            factors = set()\n",
    "            while n % 2 == 0:\n",
    "                factors.add(2)\n",
    "                n //= 2\n",
    "            for i in range(3, int(n**0.5)+1, 2):\n",
    "                while n % i == 0:\n",
    "                    factors.add(i)\n",
    "                    n //= i\n",
    "            if n > 2:\n",
    "                factors.add(n)\n",
    "            return factors\n",
    "\n",
    "        n = len(nums)\n",
    "        ufs = UFS()\n",
    "        for i in range(n):\n",
    "            ufs.add(nums[i])\n",
    "            for factor in prime_factors(nums[i]):\n",
    "                ufs.add(factor)\n",
    "                ufs.union(nums[i], factor)\n",
    "        \n",
    "        if nums.count(1) >= 2: return False\n",
    "        return len(set(ufs.find(nums[i]) for i in range(n))) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10**5\n",
    "minp = [0] * (MX + 1)\n",
    "primes = []\n",
    "for x in range(2, MX + 1):\n",
    "    if minp[x] == 0:\n",
    "        minp[x] = x\n",
    "        primes.append(x)\n",
    "    for p in primes:\n",
    "        if x * p > MX:\n",
    "            break\n",
    "        minp[x * p] = p\n",
    "        if p == minp[x]:\n",
    "            break\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        pa = list(range(n))\n",
    "\n",
    "        def find(x):\n",
    "            if pa[x] != x:\n",
    "                pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx == ry:\n",
    "                return False\n",
    "            pa[rx] = ry\n",
    "            return True\n",
    "\n",
    "        factors = {}\n",
    "        for i, x in enumerate(nums):\n",
    "            while x > 1:\n",
    "                p = minp[x]\n",
    "                if p not in factors:\n",
    "                    factors[p] = i\n",
    "                n -= union(i, factors[p])\n",
    "                while x % p == 0:\n",
    "                    x //= p\n",
    "\n",
    "        return n == 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10**5\n",
    "minp = [0] * (MX + 1)\n",
    "primes = []\n",
    "for x in range(2, MX + 1):\n",
    "    if minp[x] == 0:\n",
    "        minp[x] = x\n",
    "        primes.append(x)\n",
    "    for p in primes:\n",
    "        if x * p > MX:\n",
    "            break\n",
    "        minp[x * p] = p\n",
    "        if p == minp[x]:\n",
    "            break\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        pa = list(range(n))\n",
    "\n",
    "        def find(x):\n",
    "            if pa[x] != x:\n",
    "                pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            nonlocal n\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx != ry:\n",
    "                pa[rx] = ry\n",
    "                n -= 1\n",
    "\n",
    "        factors = {}\n",
    "        for i, x in enumerate(nums):\n",
    "            while x > 1:\n",
    "                p = minp[x]\n",
    "                if p not in factors:\n",
    "                    factors[p] = i\n",
    "                union(i, factors[p])\n",
    "                while x % p == 0:\n",
    "                    x //= p\n",
    "\n",
    "        return n == 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10**5\n",
    "minp = [0] * (MX + 1)\n",
    "primes = []\n",
    "for x in range(2, MX + 1):\n",
    "    if minp[x] == 0:\n",
    "        minp[x] = x\n",
    "        primes.append(x)\n",
    "    for p in primes:\n",
    "        if x * p > MX:\n",
    "            break\n",
    "        minp[x * p] = p\n",
    "        if p == minp[x]:\n",
    "            break\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        pa = list(range(n))\n",
    "        sz = n\n",
    "\n",
    "        def find(x):\n",
    "            if pa[x] != x:\n",
    "                pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            nonlocal sz\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx != ry:\n",
    "                pa[rx] = ry\n",
    "                sz -= 1\n",
    "\n",
    "        factors = {}\n",
    "        for i, x in enumerate(nums):\n",
    "            while x > 1:\n",
    "                p = minp[x]\n",
    "                if p not in factors:\n",
    "                    pa.append(n)\n",
    "                    factors[p] = n\n",
    "                    n += 1\n",
    "                    sz += 1\n",
    "                union(i, factors[p])\n",
    "                while x % p == 0:\n",
    "                    x //= p\n",
    "\n",
    "        return sz == 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10**5\n",
    "minp = [0] * (MX + 1)\n",
    "primes = []\n",
    "for x in range(2, MX + 1):\n",
    "    if minp[x] == 0:\n",
    "        minp[x] = x\n",
    "        primes.append(x)\n",
    "    for p in primes:\n",
    "        if x * p > MX:\n",
    "            break\n",
    "        minp[x * p] = p\n",
    "        if p == minp[x]:\n",
    "            break\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        pa = list(range(n))\n",
    "        rank = [0] * n\n",
    "\n",
    "        def find(x):\n",
    "            if pa[x] != x:\n",
    "                pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx == ry:\n",
    "                return False\n",
    "            if rank[rx] < rank[ry]:\n",
    "                rx, ry = ry, rx\n",
    "            pa[ry] = rx\n",
    "            if rank[rx] == rank[ry]:\n",
    "                rank[rx] += 1\n",
    "            return True\n",
    "\n",
    "        factors = {}\n",
    "        for i, x in enumerate(nums):\n",
    "            while x > 1:\n",
    "                p = minp[x]\n",
    "                if p in factors:\n",
    "                    n -= union(i, factors[p])\n",
    "                else:\n",
    "                    factors[p] = i\n",
    "                while x % p == 0:\n",
    "                    x //= p\n",
    "\n",
    "        return n == 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "    \n",
    "    def union(self, idx1, idx2):\n",
    "        self.parent[self.find(idx2)] = self.find(idx1)\n",
    "\n",
    "    def find(self, idx):\n",
    "        if self.parent[idx] != idx:\n",
    "            self.parent[idx] = self.find(self.parent[idx])\n",
    "        return self.parent[idx]\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        union = UnionFind(n)\n",
    "        prime = defaultdict(int)\n",
    "        for i, e in enumerate(nums):\n",
    "            if e == 1:\n",
    "                continue\n",
    "            for j in range(2, floor(sqrt(e))+1):\n",
    "                if not e % j:\n",
    "                    if prime[j]:\n",
    "                        union.union(prime[j]-1, i)\n",
    "                    if prime[e//j]:\n",
    "                        union.union(prime[e//j]-1, i)\n",
    "                    prime[j] = i+1\n",
    "                    prime[e//j] = i+1\n",
    "            if prime[e]:\n",
    "                union.union(prime[e]-1, i)\n",
    "            prime[e] = i+1\n",
    "        for i in range(1, n):\n",
    "            if union.find(i) != union.find(0):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        if len(nums) == 1: return True\n",
    "\n",
    "        dic = defaultdict(int)\n",
    "        link = list(range(len(nums) + 1))\n",
    "\n",
    "        def find(cur: int) -> int:\n",
    "            if link[cur] != cur: link[cur] = find(link[cur])\n",
    "            return link[cur]\n",
    "\n",
    "        def update(head: int, num: int) -> int:\n",
    "            if dic[num] == 0:\n",
    "                dic[num] = head\n",
    "                return head\n",
    "            else:\n",
    "                link[head] = find(dic[num])\n",
    "            return link[head]\n",
    "        \n",
    "        for idx in range(len(nums)):\n",
    "            num = nums[idx]\n",
    "            if num == 1: return False\n",
    "            end = int(sqrt(num)) + 1\n",
    "            head = update(idx + 1, num)\n",
    "            if link[head] == 0: link[head] = idx + 1\n",
    "            for fac in range(2, end):\n",
    "                if num % fac > 0: continue\n",
    "                head = update(head, fac)\n",
    "                head = update(head, num/fac)\n",
    "        \n",
    "        root = find(dic[nums[0]])\n",
    "        for num in nums:\n",
    "            if find(dic[num]) != root: return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(x):\n",
    "    ans = set()\n",
    "    y = x\n",
    "    for j in range(2, 10**9):\n",
    "        if (x%j)==0:\n",
    "            ans.add(j)\n",
    "            while (x%j)==0:\n",
    "                x //= j\n",
    "        if j*j>y:\n",
    "            break\n",
    "    if x>1:\n",
    "        ans.add(x) \n",
    "    return ans \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, a: List[int]) -> bool:\n",
    "        # a = list(set(a))\n",
    "        if len(a)==1:\n",
    "            return True \n",
    "        if 1 in a:\n",
    "            return False \n",
    "        # a = set(a)\n",
    "        g = defaultdict(set) \n",
    "        for j in a:\n",
    "            t = f(j) \n",
    "            for k in t:\n",
    "                g[j].add(-k)\n",
    "                g[-k].add(j)\n",
    "        v = {a[0]}\n",
    "        s = [a[0]] \n",
    "        num = 1 \n",
    "        while s:\n",
    "            t = []\n",
    "            for j in s:\n",
    "                for k in g[j]:\n",
    "                    if k not in v:\n",
    "                        v.add(k)\n",
    "                        t.append(k)\n",
    "                        if k>0:\n",
    "                            num += 1 \n",
    "            s = t \n",
    "        # v = {j for j in v if j>0}\n",
    "        return num==len(set(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(x):\n",
    "    ans = set()\n",
    "    y = x\n",
    "    for j in range(2, 10**9):\n",
    "        if (x%j)==0:\n",
    "            ans.add(j)\n",
    "            while (x%j)==0:\n",
    "                x //= j\n",
    "        if j*j>y:\n",
    "            break\n",
    "    if x>1:\n",
    "        ans.add(x) \n",
    "    return ans \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, a: List[int]) -> bool:\n",
    "        # a = list(set(a))\n",
    "        if len(a)==1:\n",
    "            return True \n",
    "        if 1 in a:\n",
    "            return False \n",
    "        # a = set(a)\n",
    "        g = defaultdict(set) \n",
    "        for j in a:\n",
    "            t = f(j) \n",
    "            for k in t:\n",
    "                g[j].add(-k)\n",
    "                g[-k].add(j)\n",
    "        v = {a[0]}\n",
    "        s = [a[0]] \n",
    "        while s:\n",
    "            t = []\n",
    "            for j in s:\n",
    "                for k in g[j]:\n",
    "                    if k not in v:\n",
    "                        v.add(k)\n",
    "                        t.append(k)\n",
    "            s = t \n",
    "        v = {j for j in v if j>0}\n",
    "        return len(v)==len(set(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def euler_all_primes(n):\n",
    "    is_prime = [False, False] + [True] * (n - 1)\n",
    "    primes = []\n",
    "    flg = False\n",
    "    for i in range(2, n + 1):\n",
    "        if is_prime[i]: primes.append(i)\n",
    "        if flg: continue\n",
    "        for j in primes:\n",
    "            if j * i > n: break\n",
    "            is_prime[j * i] = False\n",
    "            if i % j == 0: break\n",
    "\n",
    "    return primes\n",
    "\n",
    "primes = euler_all_primes(int((10 ** 5) ** 0.5) + 1)\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        if len(nums) == 1: return True\n",
    "        nums = list(set(nums))\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0] != 1\n",
    "\n",
    "        d = defaultdict(list)\n",
    "\n",
    "        fa = {x: x for x in nums}\n",
    "        def find(x):\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x, y):\n",
    "            fa[find(y)] = find(x)\n",
    "\n",
    "        for x in nums:\n",
    "            x0 = x\n",
    "            for p in primes:\n",
    "                if x % p != 0:\n",
    "                    continue\n",
    "                d[p].append(x0)\n",
    "                union(x0, d[p][0])\n",
    "                while x % p == 0:\n",
    "                    x //= p\n",
    "            if x > 1:\n",
    "                d[x].append(x0)  # 剩下的是超过 sqrt(10 ** 5) 的质数\n",
    "                union(x0, d[x][0])\n",
    "\n",
    "        for x in nums:\n",
    "            find(x)\n",
    "\n",
    "        return all(find(x) == find(nums[0]) for x in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def euler_all_primes(n):\n",
    "    is_prime = [False, False] + [True] * (n - 1)\n",
    "    primes = []\n",
    "    flg = False\n",
    "    for i in range(2, n + 1):\n",
    "        if is_prime[i]: primes.append(i)\n",
    "        if flg: continue\n",
    "        for j in primes:\n",
    "            if j * i > n: break\n",
    "            is_prime[j * i] = False\n",
    "            if i % j == 0: break\n",
    "\n",
    "    return primes\n",
    "\n",
    "primes = euler_all_primes(int((10 ** 5) ** 0.5) + 1)\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        if len(nums) == 1: return True\n",
    "        nums = list(set(nums))\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0] != 1\n",
    "\n",
    "        d = defaultdict(list)\n",
    "\n",
    "        fa = {x: x for x in nums}\n",
    "        def find(x):\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x, y):\n",
    "            fa[find(y)] = find(x)\n",
    "\n",
    "        for x in nums:\n",
    "            x0 = x\n",
    "            for p in primes:\n",
    "                if x % p == 0:\n",
    "                    d[p].append(x0)\n",
    "                    union(x0, d[p][0])\n",
    "                while x % p == 0:\n",
    "                    x //= p\n",
    "            if x > 1:\n",
    "                d[x].append(x0)\n",
    "                union(x0, d[x][0])\n",
    "\n",
    "        # for l in d.values():\n",
    "        #     if len(l) > 1:\n",
    "        #         for x in l[1:]:\n",
    "        #             union(x, l[0])\n",
    "        for x in nums:\n",
    "            find(x)\n",
    "\n",
    "        return all(find(x) == find(nums[0]) for x in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "m=10**5+5\n",
    "p=[[] for i in range(m)]\n",
    "for i in range(2,m):\n",
    "    if not p[i]:\n",
    "        p[i].append(i)\n",
    "        for j in range(i+i,m,i):\n",
    "            p[j].append(i)\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, a: List[int]) -> bool:\n",
    "        n=len(a)\n",
    "        ufs=list(range(n))\n",
    "        def find(x):\n",
    "            if x==ufs[x]:\n",
    "                return x\n",
    "            ufs[x]=find(ufs[x])\n",
    "            return ufs[x]\n",
    "        def union(a,b):\n",
    "            ua,ub=find(a),find(b)\n",
    "            if ua!=ub:\n",
    "                ufs[ua]=ub\n",
    "        h={}\n",
    "        for i,j in enumerate(a):\n",
    "            for k in p[j]:\n",
    "                if k in h:\n",
    "                    union(i,h[k])\n",
    "                h[k]=i\n",
    "        return all(find(i)==find(0) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [0] * n\n",
    "\n",
    "    def find(self, p):\n",
    "        while p != self.parent[p]:\n",
    "            self.parent[p] = self.parent[self.parent[p]]  # 路径压缩\n",
    "            p = self.parent[p]\n",
    "        return p\n",
    "\n",
    "    def union(self, p, q):\n",
    "        i = self.find(p)\n",
    "        j = self.find(q)\n",
    "        if i == j:\n",
    "            return\n",
    "        if self.rank[i] > self.rank[j]:\n",
    "            self.parent[j] = i\n",
    "        else:\n",
    "            self.parent[i] = j\n",
    "            if self.rank[i] == self.rank[j]:\n",
    "                self.rank[j] += 1\n",
    "\n",
    "\n",
    "maxn = 10**5 + 1\n",
    "\n",
    "class Solution:\n",
    "    fac = [[] for _ in range(maxn)]\n",
    "    for i in range(2, maxn):\n",
    "        if len(fac[i]) == 0:\n",
    "            for j in range(i, maxn, i):\n",
    "                fac[j].append(i)\n",
    "\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        if len(nums) == 1:\n",
    "            return True\n",
    "\n",
    "        nums = list(set(nums))\n",
    "        if 1 in nums:\n",
    "            return False\n",
    "\n",
    "        n = len(nums)\n",
    "        uf = UnionFind(n + maxn)\n",
    "\n",
    "        for i in range(n):\n",
    "            for p in self.fac[nums[i]]:\n",
    "                uf.union(i, p + n)\n",
    "\n",
    "        res = set()\n",
    "        for i in range(n):\n",
    "            res.add(uf.find(i))\n",
    "\n",
    "        return len(res) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(x):\n",
    "    ans = set()\n",
    "    y = x\n",
    "    for j in range(2, 10**9):\n",
    "        if (x%j)==0:\n",
    "            ans.add(j)\n",
    "            while (x%j)==0:\n",
    "                x //= j\n",
    "        if j*j>y:\n",
    "            break\n",
    "    if x>1:\n",
    "        ans.add(x) \n",
    "    return ans \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, a: List[int]) -> bool:\n",
    "        if len(a)==1:\n",
    "            return True \n",
    "        if 1 in a:\n",
    "            return False \n",
    "        g = defaultdict(set) \n",
    "        for j in a:\n",
    "            t = f(j) \n",
    "            for k in t:\n",
    "                g[j].add(str(k))\n",
    "                g[str(k)].add(j)\n",
    "        v = {a[0]}\n",
    "        s = [a[0]] \n",
    "        while s:\n",
    "            t = []\n",
    "            for j in s:\n",
    "                for k in g[j]:\n",
    "                    if k not in v:\n",
    "                        v.add(k)\n",
    "                        t.append(k)\n",
    "            s = t \n",
    "        v = {j for j in v if type(j)==int}\n",
    "        return len(v)==len(set(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(x):\n",
    "    ans = set()\n",
    "    y = x\n",
    "    for j in range(2, 10**9):\n",
    "        if (x%j)==0:\n",
    "            ans.add(j)\n",
    "            while (x%j)==0:\n",
    "                x //= j\n",
    "        if j*j>y:\n",
    "            break\n",
    "    if x>1:\n",
    "        ans.add(x) \n",
    "    return ans \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, a: List[int]) -> bool:\n",
    "        # a = list(set(a))\n",
    "        if len(a)==1:\n",
    "            return True \n",
    "        if 1 in a:\n",
    "            return False \n",
    "        # a = set(a)\n",
    "        g = defaultdict(set) \n",
    "        for j in a:\n",
    "            t = f(j) \n",
    "            for k in t:\n",
    "                g[j].add(str(k))\n",
    "                g[str(k)].add(j)\n",
    "        v = {a[0]}\n",
    "        s = [a[0]] \n",
    "        while s:\n",
    "            t = []\n",
    "            for j in s:\n",
    "                for k in g[j]:\n",
    "                    if k not in v:\n",
    "                        v.add(k)\n",
    "                        t.append(k)\n",
    "            s = t \n",
    "        v = {j for j in v if type(j)==int}\n",
    "        return len(v)==len(set(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "N = 10 ** 5 + 1\n",
    "M = defaultdict(list)\n",
    "for i in range(2, N):\n",
    "    if len(M[i]) > 0:\n",
    "        continue\n",
    "    M[i].append(i)\n",
    "    for j in range(2 * i, N, i):\n",
    "        M[j].append(i)\n",
    "class DefaultDict(dict):\n",
    "    def __missing__(self, key):\n",
    "        return key\n",
    "    \n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        for nu in nums:\n",
    "            if nu == 1:\n",
    "                if n > 1:\n",
    "                    return False\n",
    "                else:\n",
    "                    return True\n",
    "        \n",
    "        p = DefaultDict()\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        \n",
    "        s = set()\n",
    "        for nu in nums:\n",
    "            print(M[nu])\n",
    "            x_root = find(M[nu][0])\n",
    "            s.add(x_root)\n",
    "            # print(\"x_root\", x_root)\n",
    "            for j in M[nu][1:]:\n",
    "                y_root = find(j)\n",
    "                # print(\"y_root\", y_root)\n",
    "                s.add(y_root)\n",
    "                if x_root < y_root:\n",
    "                    p[y_root] = x_root\n",
    "                elif x_root > y_root:\n",
    "                    p[x_root] = y_root\n",
    "        # print(M[15])\n",
    "        # print(M[22])\n",
    "        # print(M[40])\n",
    "        # print(p)\n",
    "        return len(set((find(se) for se in s))) == 1\n",
    "\n",
    "                \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        prims = {}\n",
    "        graph = [[] for _ in range(len(nums))]\n",
    "        N = len(nums)\n",
    "        for i, v in enumerate(nums):\n",
    "            j = 2\n",
    "            while j * j <= v:\n",
    "                if v % j == 0:\n",
    "                    if j not in prims:\n",
    "                        prims[j] = N\n",
    "                        N += 1\n",
    "                        graph.append([])\n",
    "                    p = prims[j]\n",
    "                    graph[p].append(i)\n",
    "                    graph[i].append(p)\n",
    "                    while v % j == 0:\n",
    "                        v //= j\n",
    "                j += 1\n",
    "            if v > 1:\n",
    "                if v not in prims:\n",
    "                    prims[v] = N\n",
    "                    N += 1\n",
    "                    graph.append([])\n",
    "                p = prims[v]\n",
    "                graph[p].append(i)\n",
    "                graph[i].append(p)\n",
    "        visited = [False] * N\n",
    "        def dfs(x):\n",
    "            if visited[x]:\n",
    "                return\n",
    "            visited[x] = True\n",
    "            for b in graph[x]:\n",
    "                dfs(b)\n",
    "        dfs(0)\n",
    "        return all(visited[i] for i in range(len(nums)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        if len(nums) == 1:\n",
    "            return True\n",
    "        s, p = set(nums), Counter()\n",
    "        for x in s:\n",
    "            if x == 1:\n",
    "                return False\n",
    "            p[x] = x\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        ma = max(nums)\n",
    "        st = set()\n",
    "        for i in range(2, ma + 1):\n",
    "            if i in st:\n",
    "                continue\n",
    "            j = i\n",
    "            cur = -1\n",
    "            while j <= ma:\n",
    "                if j in s:\n",
    "                    if cur != -1:\n",
    "                        p[find(cur)] = find(j)\n",
    "                    cur = j \n",
    "                st.add(j)\n",
    "                j += i\n",
    "        pre = -1\n",
    "        for k, v in p.items():\n",
    "            if pre == -1:\n",
    "                pre = find(k)\n",
    "            elif find(k) != pre:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAXN = 100001\n",
    "prim_list = []\n",
    "is_prim = [True] * MAXN\n",
    "min_prim = [None] * MAXN\n",
    "next_prim = [None] * MAXN\n",
    "\n",
    "for i in range(2, MAXN):\n",
    "    if is_prim[i]:\n",
    "        min_prim[i] = i\n",
    "        next_prim[i] = 1\n",
    "        prim_list.append(i)\n",
    "    for p in prim_list:\n",
    "        v = p * i\n",
    "        if v >= MAXN:\n",
    "            break\n",
    "        is_prim[v] = False\n",
    "        min_prim[v] = p\n",
    "        if p == min_prim[i]:\n",
    "            next_prim[v] = next_prim[i]\n",
    "        else:\n",
    "            next_prim[v] = i\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        prims = {}\n",
    "        graph = [[] for _ in range(len(nums))]\n",
    "        N = len(nums)\n",
    "        for i, v in enumerate(nums):\n",
    "            while v != 1:\n",
    "                j = min_prim[v]\n",
    "                if j not in prims:\n",
    "                    prims[j] = N\n",
    "                    N += 1\n",
    "                    graph.append([])\n",
    "                p = prims[j]\n",
    "                graph[p].append(i)\n",
    "                graph[i].append(p)                \n",
    "                v = next_prim[v]\n",
    "        visited = [False] * N\n",
    "        def dfs(x):\n",
    "            if visited[x]:\n",
    "                return\n",
    "            visited[x] = True\n",
    "            for b in graph[x]:\n",
    "                dfs(b)\n",
    "        dfs(0)\n",
    "        return all(visited[i] for i in range(len(nums)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10**5\n",
    "\n",
    "lpf=list(range(MX+1))\n",
    "\n",
    "for i in range(2,int(MX**.5)+1):\n",
    "    if lpf[i] == i:\n",
    "        for j  in range(i*i,MX+1,i):\n",
    "            lpf[j]=i\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n  = len(nums)\n",
    "        parent=list(range(n))\n",
    "      \n",
    "        count =n\n",
    "\n",
    "        def find(x:int)->int:\n",
    "            if parent[x]!=x:\n",
    "                parent[x] =find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        def merge(x:int,y:int)->None:\n",
    "            px =find(x)\n",
    "            py =find(y)\n",
    "            if px!=py:\n",
    "                parent[py]=px\n",
    "                nonlocal count\n",
    "                count -=1\n",
    "\n",
    "        adj = defaultdict(set)\n",
    "        for i,x in enumerate(nums):\n",
    "            while x >1:\n",
    "                y = lpf[x]\n",
    "                while lpf[x] == y:\n",
    "                    x = x//y\n",
    "\n",
    "                adj[y].add(i)\n",
    "\n",
    "        for vals in adj.values():\n",
    "            for x,y in pairwise(vals):\n",
    "                merge(x,y)\n",
    "        \n",
    "        return count ==1\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10**5\n",
    "\n",
    "lpf=list(range(MX+1))\n",
    "\n",
    "for i in range(2,int(MX**.5)+1):\n",
    "    if lpf[i] == i:\n",
    "        for j  in range(i*i,MX+1,i):\n",
    "            lpf[j]=i\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n  = len(nums)\n",
    "        parent=list(range(n))\n",
    "      \n",
    "        count =n\n",
    "\n",
    "        def find(x:int)->int:\n",
    "            if parent[x]!=x:\n",
    "                parent[x] =find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        def merge(x:int,y:int)->None:\n",
    "            px =find(x)\n",
    "            py =find(y)\n",
    "            if px!=py:\n",
    "                parent[py]=px\n",
    "                nonlocal count\n",
    "                count -=1\n",
    "\n",
    "        adj = defaultdict(set)\n",
    "        for i,x in enumerate(nums):\n",
    "            while x >1:\n",
    "                y = lpf[x]\n",
    "                while lpf[x] == y:\n",
    "                    x = x//y\n",
    "\n",
    "                adj[y].add(i)\n",
    "\n",
    "        for vals in adj.values():\n",
    "            for x,y in pairwise(vals):\n",
    "                merge(x,y)\n",
    "        \n",
    "        return count ==1\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        prims = {}\n",
    "        graph = [[] for _ in range(len(nums))]\n",
    "        N = len(nums)\n",
    "        for i, v in enumerate(nums):\n",
    "            j = 2\n",
    "            while j * j <= v:\n",
    "                if v % j == 0:\n",
    "                    if j not in prims:\n",
    "                        prims[j] = N\n",
    "                        N += 1\n",
    "                        graph.append([])\n",
    "                    p = prims[j]\n",
    "                    graph[p].append(i)\n",
    "                    graph[i].append(p)\n",
    "                    while v % j == 0:\n",
    "                        v //= j\n",
    "                j += 1\n",
    "            if v > 1:\n",
    "                if v not in prims:\n",
    "                    prims[v] = N\n",
    "                    N += 1\n",
    "                    graph.append([])\n",
    "                p = prims[v]\n",
    "                graph[p].append(i)\n",
    "                graph[i].append(p)\n",
    "        print(graph)\n",
    "        visited = [False] * N\n",
    "        def dfs(x):\n",
    "            if visited[x]:\n",
    "                return\n",
    "            visited[x] = True\n",
    "            for b in graph[x]:\n",
    "                dfs(b)\n",
    "        dfs(0)\n",
    "        return all(visited[i] for i in range(len(nums)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "import itertools\n",
    "from sortedcontainers import SortedSet\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.parents = [i for i in range(n)]\n",
    "        self.cnts = [1] * n\n",
    "        self.division_cnt = n\n",
    "        \n",
    "    def union(self, num1, num2):\n",
    "        parent1, parent2 = self.find(num1), self.find(num2)\n",
    "        if parent1 == parent2:\n",
    "            return\n",
    "        if parent1 < parent2:\n",
    "            self.parents[parent2] = parent1\n",
    "            self.cnts[parent1] += self.cnts[parent2]\n",
    "        else:\n",
    "            self.parents[parent1] = parent2\n",
    "            self.cnts[parent2] += self.cnts[parent1]\n",
    "        self.division_cnt -= 1\n",
    "    \n",
    "    def find(self, num):\n",
    "        if num != self.parents[num]:\n",
    "            self.parents[num] = self.find(self.parents[num])\n",
    "        return self.parents[num]\n",
    "        # while num != self.parents[num]:\n",
    "        #     self.parents[num] = self.parents[self.parents[num]]\n",
    "        #     num = self.parents[num]\n",
    "        # return num\n",
    "\n",
    "factors = defaultdict(list)\n",
    "max_n = 10 ** 5 + 1\n",
    "for i in range(2, max_n):\n",
    "    if len(factors[i]) == 0:\n",
    "        for j in range(i, max_n, i):\n",
    "            factors[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        uf = UnionFind(n + max_n)\n",
    "        for i, num in enumerate(nums):\n",
    "            for j in factors[num]:\n",
    "                uf.union(i, n + j)\n",
    "        \n",
    "        parent_set = set()\n",
    "        for i, num in enumerate(nums):\n",
    "            parent_set.add(uf.find(i))\n",
    "            if len(parent_set) > 1:\n",
    "                return False\n",
    "        return len(parent_set) == 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class NumberTheoryPrimeFactor:\n",
    "    def __init__(self, ceil):\n",
    "        self.ceil = ceil + 100\n",
    "        self.prime_factor = [[] for _ in range(self.ceil + 1)]\n",
    "        self.min_prime = [0] * (self.ceil + 1)\n",
    "        self.get_min_prime_and_prime_factor()\n",
    "        return\n",
    "\n",
    "    def get_min_prime_and_prime_factor(self):\n",
    "        # 模板：计算 1 到 self.ceil 所有数字的最小质数因子\n",
    "        for i in range(2, self.ceil + 1):\n",
    "            if not self.min_prime[i]:\n",
    "                self.min_prime[i] = i\n",
    "                for j in range(i * i, self.ceil + 1, i):\n",
    "                    if not self.min_prime[j]:\n",
    "                        self.min_prime[j] = i\n",
    "\n",
    "        # 模板：计算 1 到 self.ceil 所有数字的质数分解（可选）\n",
    "        for num in range(2, self.ceil + 1):\n",
    "            i = num\n",
    "            while num > 1:\n",
    "                p = self.min_prime[num]\n",
    "                cnt = 0\n",
    "                while num % p == 0:\n",
    "                    num //= p\n",
    "                    cnt += 1\n",
    "                self.prime_factor[i].append([p, cnt])\n",
    "        return\n",
    "\n",
    "    def comb(self, n, m):\n",
    "        cnt = defaultdict(int)\n",
    "        for i in range(1, n + 1):  # n!\n",
    "            for num, y in self.prime_factor[i]:\n",
    "                cnt[num] += y\n",
    "        for i in range(1, m + 1):  # m!\n",
    "            for num, y in self.prime_factor[i]:\n",
    "                cnt[num] -= y\n",
    "        for i in range(1, n - m + 1):  # (n-m)!\n",
    "            for num, y in self.prime_factor[i]:\n",
    "                cnt[num] -= y\n",
    "\n",
    "        ans = 1\n",
    "        for w in cnt:\n",
    "            ans *= w ** cnt[w]\n",
    "        return ans\n",
    "\n",
    "nt = NumberTheoryPrimeFactor(10**5+10)\n",
    "# 标准并查集\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.part = n\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        uf = UnionFind(n)\n",
    "        pre = dict()\n",
    "        for i, num in enumerate(nums):\n",
    "            for p, _ in nt.prime_factor[num]:\n",
    "                if p in pre:\n",
    "                    uf.union(pre[p], i)\n",
    "                else:\n",
    "                    pre[p] = i\n",
    "        return uf.part == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "A=list()\n",
    "memo={1:{1}}\n",
    "for i in range(2,10**5+1):\n",
    "    s=i\n",
    "    L=set()\n",
    "    flag=0\n",
    "    for j in A:\n",
    "        if j*j>i:\n",
    "            break\n",
    "        if i%j==0:\n",
    "            flag=1\n",
    "            while i%j==0:\n",
    "                i=i//j\n",
    "            L.add(j)\n",
    "    if flag==0:\n",
    "        A.append(i)\n",
    "    if i!=1:\n",
    "        L.add(i)\n",
    "    memo[s]=L  \n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        dic=dict()\n",
    "        for i in range(len(nums)):\n",
    "            for j in memo[nums[i]]:\n",
    "                s=dic.get(j,[])\n",
    "                s.append(i)\n",
    "                dic[j]=s\n",
    "        father=[i for i in range(len(nums))]\n",
    "        def find(x):\n",
    "            if x==father[x]:\n",
    "                return x\n",
    "            else:\n",
    "                father[x]=find(father[x])\n",
    "                return father[x]\n",
    "        def union(x,y):\n",
    "            father[find(y)]=find(x)\n",
    "        for i in dic:\n",
    "            if i==1:\n",
    "                continue\n",
    "            L=dic[i]\n",
    "            if len(L)>1:\n",
    "                for j in range(1,len(L)):\n",
    "                    if find(L[0])!=find(L[j]):\n",
    "                        union(L[0],L[j])\n",
    "        s=find(0)\n",
    "        for i in range(1,len(nums)):\n",
    "            if s!=find(i):\n",
    "                return False\n",
    "        return True\n",
    "            \n",
    "                \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10**5\n",
    "\n",
    "lpf=list(range(MX+1))\n",
    "\n",
    "for i in range(2,int(MX**.5)+1):\n",
    "    if lpf[i] == i:\n",
    "        for j  in range(i*i,MX+1,i):\n",
    "            lpf[j]=i\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n  = len(nums)\n",
    "        parent=list(range(n))\n",
    "      \n",
    "        count =n\n",
    "\n",
    "        def find(x:int)->int:\n",
    "            if parent[x]!=x:\n",
    "                parent[x] =find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        def merge(x:int,y:int)->None:\n",
    "            px =find(x)\n",
    "            py =find(y)\n",
    "            if px!=py:\n",
    "                parent[px]=py\n",
    "                nonlocal count\n",
    "                count -=1\n",
    "\n",
    "        adj = defaultdict(set)\n",
    "        for i,x in enumerate(nums):\n",
    "            while x >1:\n",
    "                y = lpf[x]\n",
    "                while lpf[x] == y:\n",
    "                    x = x//y\n",
    "\n",
    "                adj[y].add(i)\n",
    "\n",
    "        for vals in adj.values():\n",
    "            for x,y in pairwise(vals):\n",
    "                merge(x,y)\n",
    "        \n",
    "        return count ==1\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10**5\n",
    "lpf = list(range(N + 1))  # 最小质因数 埃式筛法 lpf[x]==x表示质数\n",
    "for x in range(2, int(N**.5) + 1):\n",
    "    if lpf[x] == x:\n",
    "        for y in range(x * x, N + 1, x):\n",
    "            lpf[y] = x\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        roots = list(range(n))\n",
    "        count = n\n",
    "\n",
    "        def find(x):\n",
    "            if roots[x] != x:\n",
    "                roots[x] = find(roots[x])\n",
    "            return roots[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx != ry:\n",
    "                roots[rx] = ry  # rx -> ry\n",
    "                nonlocal count\n",
    "                count -= 1\n",
    "\n",
    "        adj = defaultdict(set)\n",
    "        for i, x in enumerate(nums):\n",
    "            while x > 1:\n",
    "                p = lpf[x]\n",
    "                adj[p].add(i)\n",
    "                x //= p\n",
    "        for vals in adj.values():\n",
    "            for x, y in pairwise(vals):\n",
    "                union(x, y)\n",
    "        return count == 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10**5\n",
    "lpf = list(range(N + 1))  \n",
    "for x in range(2, int(N**.5) + 1):\n",
    "    if lpf[x] == x:\n",
    "        for y in range(x * x, N + 1, x):\n",
    "            lpf[y] = x\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        roots = list(range(n))\n",
    "        count = n\n",
    "        def find(x):\n",
    "            if roots[x] != x:\n",
    "                roots[x] = find(roots[x])\n",
    "            return roots[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx != ry:\n",
    "                roots[rx] = ry  \n",
    "                nonlocal count\n",
    "                count -= 1\n",
    "\n",
    "        adj = defaultdict(set)\n",
    "        for i, x in enumerate(nums):\n",
    "            while x > 1:\n",
    "                p = lpf[x]\n",
    "                adj[p].add(i)\n",
    "                x //= p\n",
    "        for vals in adj.values():\n",
    "            for x, y in pairwise(vals):\n",
    "                union(x, y)\n",
    "        return count == 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10**5\n",
    "lpf = list(range(N + 1))  # 最小质因数 埃式筛法 lpf[x]==x表示质数\n",
    "for x in range(2, int(N**.5) + 1):\n",
    "    if lpf[x] == x:\n",
    "        for y in range(x * x, N + 1, x):\n",
    "            lpf[y] = x\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        roots = list(range(n))\n",
    "        count = n\n",
    "\n",
    "        def find(x):\n",
    "            if roots[x] != x:\n",
    "                roots[x] = find(roots[x])\n",
    "            return roots[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx != ry:\n",
    "                roots[rx] = ry  # rx -> ry\n",
    "                nonlocal count\n",
    "                count -= 1\n",
    "\n",
    "        adj = defaultdict(set)\n",
    "        for i, x in enumerate(nums):\n",
    "            while x > 1:\n",
    "                p = lpf[x]\n",
    "                adj[p].add(i)\n",
    "                x //= p\n",
    "        for vals in adj.values():\n",
    "            for x, y in pairwise(vals):\n",
    "                union(x, y)\n",
    "        return count == 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10**5\n",
    "lpf = list(range(N + 1))  # 最小质因数 埃式筛法 lpf[x]==x表示质数\n",
    "for x in range(2, int(N**.5) + 1):\n",
    "    if lpf[x] == x:\n",
    "        for y in range(x * x, N + 1, x):\n",
    "            lpf[y] = x\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        roots = list(range(n))\n",
    "        count = n\n",
    "\n",
    "        def find(x):\n",
    "            if roots[x] != x:\n",
    "                roots[x] = find(roots[x])\n",
    "            return roots[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx != ry:\n",
    "                roots[rx] = ry  # rx -> ry\n",
    "                nonlocal count\n",
    "                count -= 1\n",
    "\n",
    "        adj = defaultdict(set)\n",
    "        for i, x in enumerate(nums):\n",
    "            while x > 1:\n",
    "                p = lpf[x]\n",
    "                adj[p].add(i)\n",
    "                x //= p\n",
    "        for vals in adj.values():\n",
    "            for x, y in pairwise(vals):\n",
    "                union(x, y)\n",
    "        return count == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10**5\n",
    "lpf = list(range(MX+1))\n",
    "\n",
    "for i in range(2,MX+1):\n",
    "    if lpf[i] == i:\n",
    "        for j in range(i*i,MX,i): \n",
    "            lpf[j] = i\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "\n",
    "        parent=list(range(n))\n",
    "        count =n\n",
    "\n",
    "        def find(x:int)->int:\n",
    "            if x != parent[x]:\n",
    "                parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        def merge(x:int,y:int)->None:\n",
    "            px,py = find(x),find(y)\n",
    "\n",
    "            if px !=py:\n",
    "                nonlocal count\n",
    "                parent[px] = py\n",
    "                count -=1\n",
    "\n",
    "        g = defaultdict(set)\n",
    "        for i,x in enumerate(nums):\n",
    "            while x>1:\n",
    "                y = lpf[x]\n",
    "                while lpf[x]==y:\n",
    "                    x //=y\n",
    "                g[y].add(i)\n",
    "\n",
    "\n",
    "        for vals in g.values():\n",
    "            for x,y in pairwise(vals):\n",
    "                merge(x,y)\n",
    "        print(count) \n",
    "        return count==1\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        if nums == [1]:\n",
    "            return True\n",
    "        if set(nums) == {1}:\n",
    "            return False\n",
    "        if len(set(nums)) == 1:\n",
    "            return True\n",
    "\n",
    "        nums = list(set(nums))\n",
    "\n",
    "        from collections import defaultdict\n",
    "        g = defaultdict(list)\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    g[num].append(i)\n",
    "                    g[num].append(num // i)\n",
    "                    g[i].append(num)\n",
    "                    g[num // i].append(num)\n",
    "                i += 1\n",
    "\n",
    "        used = defaultdict(bool)\n",
    "        def dfs(u):\n",
    "            used[u] = True\n",
    "            for v in g[u]:\n",
    "                if not used[v]:\n",
    "                    dfs(v)\n",
    "\n",
    "        dfs(nums[0])\n",
    "        for num in nums:\n",
    "            if used[num] == False:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        if nums == [1]:\n",
    "            return True\n",
    "        if set(nums) == {1}:\n",
    "            return False\n",
    "        if len(set(nums)) == 1:\n",
    "            return True\n",
    "\n",
    "        nums = list(set(nums))\n",
    "\n",
    "        from collections import defaultdict\n",
    "        g = defaultdict(list)\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    g[num].append(i)\n",
    "                    g[num].append(num // i)\n",
    "                    g[i].append(num)\n",
    "                    g[num // i].append(num)\n",
    "                i += 1\n",
    "\n",
    "        used = defaultdict(bool)\n",
    "        def dfs(u):\n",
    "            used[u] = True\n",
    "            for v in g[u]:\n",
    "                if not used[v]:\n",
    "                    dfs(v)\n",
    "\n",
    "        dfs(nums[0])\n",
    "        for num in nums:\n",
    "            if used[num] == False:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAXN = 10**5 + 10\n",
    "fact = [[] for _ in range(MAXN)]\n",
    "is_p = [False] * MAXN\n",
    "for i in range(2, MAXN):\n",
    "    if not is_p[i]:\n",
    "        is_p[i] = True\n",
    "        for j in range(i, MAXN, i):\n",
    "            is_p[j] = True\n",
    "            fact[j].append(i)\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        mx = max(nums)\n",
    "        fa = list(range(n + mx + 1))\n",
    "\n",
    "        def find(x):\n",
    "            #print(x)\n",
    "            if fa[x] != x: fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        def merge(a, b):\n",
    "            pa, pb = find(a), find(b)\n",
    "            fa[pa] = pb\n",
    "        \n",
    "        for i in range(n):\n",
    "            for x in fact[nums[i]]:\n",
    "                #print(x + n)\n",
    "                merge(i, x + n)\n",
    "        \n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            s.add(find(i))\n",
    "        return len(s) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def euler_all_primes(n):\n",
    "    is_prime = [False, False] + [True] * (n - 1)\n",
    "    primes = []\n",
    "    flg = False\n",
    "    for i in range(2, n + 1):\n",
    "        if is_prime[i]: primes.append(i)\n",
    "        if flg: continue\n",
    "        for j in primes:\n",
    "            if j * i > n: break\n",
    "            is_prime[j * i] = False\n",
    "            if i % j == 0: break\n",
    "\n",
    "    return primes\n",
    "\n",
    "primes = euler_all_primes(int((10 ** 5) ** 0.5) + 1)\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        if len(nums) == 1: return True\n",
    "        nums = list(set(nums))\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0] != 1\n",
    "\n",
    "        d = defaultdict(list)\n",
    "\n",
    "        for x in nums:\n",
    "            x0 = x\n",
    "            for p in primes:\n",
    "                if x % p == 0:\n",
    "                    d[p].append(x0)\n",
    "                while x % p == 0:\n",
    "                    x //= p\n",
    "            if x > 1:\n",
    "                d[x].append(x0)\n",
    "\n",
    "\n",
    "        fa = {x: x for x in nums}\n",
    "        def find(x):\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x, y):\n",
    "            fa[find(y)] = find(x)\n",
    "\n",
    "        for l in d.values():\n",
    "            if len(l) > 1:\n",
    "                for x in l[1:]:\n",
    "                    union(x, l[0])\n",
    "        for x in nums:\n",
    "            find(x)\n",
    "\n",
    "        return all(find(x) == find(nums[0]) for x in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        if nums == [1]:\n",
    "            return True\n",
    "        if set(nums) == {1}:\n",
    "            return False\n",
    "        if len(set(nums)) == 1:\n",
    "            return True\n",
    "\n",
    "        from collections import defaultdict\n",
    "        g = defaultdict(list)\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            flag = True\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    flag = False\n",
    "                    g[num].append(i)\n",
    "                    g[num].append(num // i)\n",
    "                    g[i].append(num)\n",
    "                    g[num // i].append(num)\n",
    "                i += 1\n",
    "            if flag:\n",
    "                cnt += 1\n",
    "        if cnt == len(nums):\n",
    "            return False\n",
    "        used = defaultdict(bool)\n",
    "\n",
    "        def dfs(u):\n",
    "            used[u] = True\n",
    "            for v in g[u]:\n",
    "                if not used[v]:\n",
    "                    dfs(v)\n",
    "\n",
    "        dfs(nums[0])\n",
    "        for num in nums:\n",
    "            if used[num] == False:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        p = list(range(n))\n",
    "        def find(x):\n",
    "            if p[x] == x:\n",
    "                return x\n",
    "            p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        for i in range(n):\n",
    "            if gcd(nums[i], nums[i-1]) > 1:\n",
    "                p[find(i-1)] = find(i)\n",
    "        for x, y in pairwise(set(p)):\n",
    "            if gcd(nums[x], nums[y]) > 1:\n",
    "                p[find(y)] = find(x)\n",
    "        for i in range(n):\n",
    "            find(i)\n",
    "        return len(set(p)) == 1\n",
    "\n",
    "n = 10 ** 5 + 1\n",
    "primes = [[] for _ in range(n)]\n",
    "for i in range(2, n):\n",
    "    if not primes[i]:\n",
    "        for j in range(i, n, i):\n",
    "            primes[j].append(i)\n",
    "            \n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        m = len(nums)\n",
    "        p = list(range(n + m))\n",
    "        def find(x):\n",
    "            if p[x] == x:\n",
    "                return x\n",
    "            p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        for i in range(m):\n",
    "            for prime in primes[nums[i]]:\n",
    "                p[find(m + prime)] = find(i)\n",
    "        ret = set()\n",
    "        for i in range(m):\n",
    "            ret.add(find(i))\n",
    "        return len(ret) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "maxn = 10 ** 5 + 1\n",
    "fac = [[] for _ in range(maxn)]\n",
    "for i in range(2, maxn):\n",
    "    if len(fac[i]) == 0:\n",
    "        for j in range(i, maxn, i):\n",
    "            fac[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n==1:\n",
    "            return True\n",
    "        fa = list(range(maxn))\n",
    "        temp=[False]*maxn\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x: int, y: int):\n",
    "            fx, fy = find(x), find(y)\n",
    "            if fx != fy:\n",
    "                fa[fy] = fx\n",
    "        ma=-1\n",
    "        for i in range(n):\n",
    "            if nums[i]==1:\n",
    "                return False\n",
    "            for p in fac[nums[i]]:\n",
    "                temp[p]=True\n",
    "                union(fac[nums[i]][0], p)\n",
    "                ma=max(ma,p)\n",
    "        res = set()\n",
    "        for i in range(ma+1):\n",
    "            if temp[i]:\n",
    "                res.add(find(i))\n",
    "        return len(res)==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "hashmap = defaultdict(list)\n",
    "N = 10 ** 5 + 1\n",
    "for i in range(2,N):\n",
    "    for j in range(i,N,i):\n",
    "        hashmap[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        \n",
    "        parents = list(range(N))\n",
    "\n",
    "        def find(x):\n",
    "            if x != parents[x]:\n",
    "                parents[x] = find(parents[x])\n",
    "            return parents[x]\n",
    "\n",
    "        def union(u,v):\n",
    "            x , y = find(u) , find(v)\n",
    "            if x != y:\n",
    "                parents[x] = y\n",
    "        \n",
    "        for num in nums:\n",
    "            for x in hashmap[num]:\n",
    "                union(num,x)\n",
    "        \n",
    "        cnts = Counter()\n",
    "        for num in nums:\n",
    "            cnts[find(num)] += 1\n",
    "        if cnts[1] > 0 and len(nums) > 1:return False\n",
    "        return len(cnts) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10**5\n",
    "\n",
    "lpf=list(range(MX+1))\n",
    "\n",
    "for i in range(2,int(MX**.5)+1):\n",
    "    if lpf[i] == i:\n",
    "        for j  in range(i*i,MX+1,i):\n",
    "            lpf[j]=i\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n  = len(nums)\n",
    "        parent=[0]*(n+MX)\n",
    "        for i in range(len(parent)):\n",
    "            parent[i] = i\n",
    "\n",
    "        def find(x:int)->int:\n",
    "            if parent[x]!=x:\n",
    "                parent[x] =find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        def merge(x:int,y:int)->None:\n",
    "            px =find(x)\n",
    "            py =find(y)\n",
    "            if px!=py:\n",
    "                parent[px]=py\n",
    "\n",
    "        for i,x in enumerate(nums):\n",
    "            while x >1:\n",
    "                y = lpf[x]\n",
    "                while lpf[x] == y:\n",
    "                    x = x//y\n",
    "                merge(i,n+y)\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if find(0)!=find(i):\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "maxn = 10 ** 5 + 1\n",
    "fac = [[] for _ in range(maxn)]\n",
    "for i in range(2, maxn):\n",
    "    if len(fac[i]) == 0:\n",
    "        for j in range(i, maxn, i):\n",
    "            fac[j].append(i)\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        fa = [i for i in range(n + maxn)]\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x: int, y: int):\n",
    "            fx, fy = find(x), find(y)\n",
    "            if fx != fy:\n",
    "                fa[fy] = fx\n",
    "        \n",
    "        for i in range(n):\n",
    "            for p in fac[nums[i]]:\n",
    "                union(i, n + p)\n",
    "        res = set()\n",
    "        for i in range(n):\n",
    "            res.add(find(i))\n",
    "        return len(res) == 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10**5\n",
    "\n",
    "lpf=[0]*(MX+1)\n",
    "\n",
    "for i in range(2,MX+1):\n",
    "    if lpf[i]==0:\n",
    "        for j  in range(i,MX+1,i):\n",
    "            lpf[j]=i\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n  = len(nums)\n",
    "        parent=[0]*(n+MX)\n",
    "        for i in range(len(parent)):\n",
    "            parent[i] = i\n",
    "\n",
    "        def find(x:int)->int:\n",
    "            if parent[x]!=x:\n",
    "                parent[x] =find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        def merge(x:int,y:int)->None:\n",
    "            px =find(x)\n",
    "            py =find(y)\n",
    "            if px!=py:\n",
    "                parent[px]=py\n",
    "\n",
    "        for i,x in enumerate(nums):\n",
    "            while x >1:\n",
    "                y = lpf[x]\n",
    "                while lpf[x] == y:\n",
    "                    x = x//y\n",
    "                merge(i,n+y)\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if find(0)!=find(i):\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10**5\n",
    "\n",
    "lpf=[0]*(MX+1)\n",
    "\n",
    "for i in range(2,MX+1):\n",
    "    if lpf[i]==0:\n",
    "        for j  in range(i,MX+1,i):\n",
    "            lpf[j]=i\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n  = len(nums)\n",
    "        parent=[0]*(n+MX)\n",
    "        for i in range(len(parent)):\n",
    "            parent[i] = i\n",
    "\n",
    "        def find(x:int)->int:\n",
    "            if parent[x]!=x:\n",
    "                parent[x] =find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        def merge(x:int,y:int)->None:\n",
    "            px =find(x)\n",
    "            py =find(y)\n",
    "            if px!=py:\n",
    "                parent[px]=py\n",
    "\n",
    "        for i,x in enumerate(nums):\n",
    "            while x >1:\n",
    "                y = lpf[x]\n",
    "                while lpf[x] == y:\n",
    "                    x = x//y\n",
    "                merge(i,n+y)\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if find(0)!=find(i):\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "max_n = 10**5 + 1\n",
    "fac = [[] for _ in range(max_n)]\n",
    "for i in range(2,max_n):\n",
    "    if len(fac[i]) == 0:\n",
    "        for j in range(i, max_n, i):\n",
    "            fac[j].append(i)\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        fa = [i for i in range(n + max_n)]\n",
    "        def find(x:int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x:int, y:int):\n",
    "            fx, fy = find(x), find(y)\n",
    "            if fx != fy:\n",
    "                fa[fy] = fx\n",
    "        for i in range(n):\n",
    "            for p in fac[nums[i]]:\n",
    "                union(i, n+p)\n",
    "        res = set()\n",
    "        for i in range(n):\n",
    "            res.add(find(i))\n",
    "        if len(res) == 1:\n",
    "            return True\n",
    "        return False\n",
    "             \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "maxn = 10 ** 5 + 1\n",
    "fac = [[] for _ in range(maxn)]\n",
    "for i in range(2, maxn):\n",
    "    if len(fac[i]) == 0:\n",
    "        for j in range(i, maxn, i):\n",
    "            fac[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        fa = [i for i in range(n + maxn)]\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x: int, y: int):\n",
    "            fx, fy = find(x), find(y)\n",
    "            if fx != fy:\n",
    "                fa[fy] = fx\n",
    "        \n",
    "        for i in range(n):\n",
    "            for p in fac[nums[i]]:\n",
    "                union(i, n + p)\n",
    "        res = set()\n",
    "        for i in range(n):\n",
    "            res.add(find(i))\n",
    "        if len(res) == 1: return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "maxn = 10 ** 5 + 1\n",
    "fac = [[] for _ in range(maxn)]\n",
    "for i in range(2, maxn):\n",
    "    if len(fac[i]) == 0:\n",
    "        for j in range(i, maxn, i):\n",
    "            fac[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        fa = [i for i in range(n + maxn)]\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x: int, y: int):\n",
    "            fx, fy = find(x), find(y)\n",
    "            if fx != fy:\n",
    "                fa[fy] = fx\n",
    "        \n",
    "        for i in range(n):\n",
    "            for p in fac[nums[i]]:\n",
    "                union(i, n + p)\n",
    "        res = set()\n",
    "        for i in range(n):\n",
    "            res.add(find(i))\n",
    "        if len(res) == 1: return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "maxn = 10 ** 5 + 1\n",
    "fac = [[] for _ in range(maxn)]\n",
    "for i in range(2, maxn):\n",
    "    if len(fac[i]) == 0:\n",
    "        for j in range(i, maxn, i):\n",
    "            fac[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        fa = [i for i in range(n + maxn)]\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x: int, y: int):\n",
    "            fx, fy = find(x), find(y)\n",
    "            if fx != fy:\n",
    "                fa[fy] = fx\n",
    "        \n",
    "        for i in range(n):\n",
    "            for p in fac[nums[i]]:\n",
    "                union(i, n + p)\n",
    "        res = set()\n",
    "        for i in range(n):\n",
    "            res.add(find(i))\n",
    "        if len(res) == 1: return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "maxn = 10 ** 5 + 1\n",
    "fac = [[] for _ in range(maxn)]\n",
    "for i in range(2, maxn):\n",
    "    if len(fac[i]) == 0:\n",
    "        for j in range(i, maxn, i):\n",
    "            fac[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        fa = [i for i in range(n + maxn)]\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x: int, y: int):\n",
    "            fx, fy = find(x), find(y)\n",
    "            if fx != fy:\n",
    "                fa[fy] = fx\n",
    "        \n",
    "        for i in range(n):\n",
    "            for p in fac[nums[i]]:\n",
    "                union(i, n + p)\n",
    "        res = set()\n",
    "        for i in range(n):\n",
    "            res.add(find(i))\n",
    "        if len(res) == 1: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "maxn = 10 ** 5 + 1\n",
    "fac = [[] for _ in range(maxn)]\n",
    "for i in range(2, maxn):\n",
    "    if len(fac[i]) == 0:\n",
    "        for j in range(i, maxn, i):\n",
    "            fac[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        fa = [i for i in range(n + maxn)]\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x: int, y: int):\n",
    "            fx, fy = find(x), find(y)\n",
    "            if fx != fy:\n",
    "                fa[fy] = fx\n",
    "\n",
    "        for i in range(n):\n",
    "            for p in fac[nums[i]]:\n",
    "                union(i, n + p)\n",
    "\n",
    "        res = set()\n",
    "        for i in range(n):\n",
    "            res.add(find(i))\n",
    "        if len(res) == 1: return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTraverseAllPairs(self, nums: List[int]) -> bool:\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        def union(a, b):\n",
    "            p[find(a)] = find(b)\n",
    "            \n",
    "        if len(nums) == 1:\n",
    "            return True\n",
    "        M = 100010\n",
    "        p = [i for i in range(M)]\n",
    "        s = set()\n",
    "        for i, v in enumerate(nums):\n",
    "            if v == 1:\n",
    "                return False\n",
    "            if v in s:\n",
    "                continue\n",
    "            s.add(v)\n",
    "            x = 2\n",
    "            while x * x <= v:\n",
    "                if v % x == 0:\n",
    "                    union(nums[i], x)\n",
    "                    while v % x == 0:\n",
    "                        v //= x\n",
    "                x += 1\n",
    "            if v > 1 and nums[i] != v:\n",
    "                union(nums[i], v)\n",
    "        common = find(nums[0])\n",
    "        for v in nums:\n",
    "            if find(v) != common:\n",
    "                return False\n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
